using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace SuchAlgorithmen
{
    public class HeapSort : SuchAlgorithmen.ISorter
    {
        private ArrayList _unsortierteliste;
        private ArrayList _sortierteliste;
        private int _heapGroesse;

        
        /// <summary>
        /// Konstruktor der Klasse Heapsort, es wird als Parameter eine Liste verlangt, die
        /// in der weiteren Anwendung benutzt wird
        /// </summary>
        /// <param name="array">Das zu sortierende Array</param>
        public HeapSort(ArrayList array)
        {
            _unsortierteliste   = new ArrayList(array);
            _heapGroesse        = _unsortierteliste.Count - 1;
            _sortierteliste     = new ArrayList(_heapGroesse);

        }

        //public methoden

        /// <summary>
        /// Gibt den Wert in der Liste mit index i 
        /// </summary>
        /// <param name="index">Index i</param>
        /// <returns>int Den Wert in der Liste mit index i</returns>
        public int this[int index]
	    {
            get { return (int)_sortierteliste[index]; }
	    }
	
        
        /// <summary>
        /// Gibt die Laenge der Liste zurueck
        /// </summary>
        /// <returns>int</returns>
        public int GetListLenght(){
            return _sortierteliste.Count;
        }
                       

        /// <summary>
        /// Sortiert die Liste
        /// </summary>
        /// <returns>void</returns>
        public void Sort()
        {
            BuildMaxHeap();
            for (int i = _unsortierteliste.Count - 1; i > 1; i--)
            {
                _sortierteliste.Add(_unsortierteliste[1]);
                Swap(_unsortierteliste, 1, i);
                MaxHeapify(_unsortierteliste.GetRange(0, i - 1), 1);
            }
        }

        //private methoden
        private int LeftChild(int i)
        {
            return 2*i;
        }

        private int RightChild(int i)
        {
            return 2*i+1;
        }

        private int ParentNode(int i)
        {
            return (i / 2);
        }

        private void BuildMaxHeap()
        {
            _heapGroesse = _unsortierteliste.Count - 1;
            int maxbound = (int)Math.Floor((Double)(_unsortierteliste.Count - 1) / 2);
            for (int i = maxbound; i >= 1; i--)
            {
                MaxHeapify(_unsortierteliste, i);
            }
        }

        private void MaxHeapify(ArrayList liste, int i)
        {
            int left = LeftChild(i);
            int right = RightChild(i);
            int maximum;

            if (left < liste.Count && (int)liste[left] < (int)liste[i])
            {
                maximum = left;
            }
            else
            {
                maximum = i;
            }
            if (right < liste.Count && (int)liste[right] < (int)liste[maximum])
            {
                maximum = right;
            }
            if (maximum != i)
            {
                Swap(liste, i, maximum);
                MaxHeapify(liste,maximum);
            }
        }

        private void Swap(ArrayList liste, int i, int j)
        {
            int z = (int)liste[i];
            liste[i] = liste[j];
            liste[j] = z;
        }

        /* old version
         * 
         * 
        public void Sort()
        {
            while (_unsortierteliste.Count > 1)
	        {
        	   BuildMaxHeap();
               _sortierteliste.Add(_unsortierteliste[1]);
               _unsortierteliste[1] = _unsortierteliste[_unsortierteliste.Count-1];
               _unsortierteliste.RemoveAt(_unsortierteliste.Count-1);
	        }
        }
         * 
         *  private void Swap(int i, int j)
        {
            int z = (int)_unsortierteliste[i];
            _unsortierteliste[i] = _unsortierteliste[j];
            _unsortierteliste[j] = z;
        }
         * 
         private void BuildMaxHeap()
        {
            _heapGroesse = _unsortierteliste.Count - 1;
            int maxbound = ((_unsortierteliste.Count - 1) / 2);
            for (int i = maxbound; i >= 1; i--)
            {
                MaxHeapify(i);
            }
        }
          
        private void MaxHeapify(Arraint i)
        {
            int left = LeftChild(i);
            int right = RightChild(i);
            int maximum;

            if (left <= _heapGroesse && (int)_unsortierteliste[left] < (int)_unsortierteliste[i])
            {
                maximum = left;   
            }
            else
            {
                maximum = i;
            }
            if (right <= _heapGroesse && (int)_unsortierteliste[right] < (int)_unsortierteliste[maximum])
            {
                maximum = right;
            }
            if (maximum != i)
            {
                Swap(i, maximum);
                MaxHeapify(maximum);
            }
        }
        */





    }
}
